from cmath import inf
from typing import *


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)

        def f(id: int):
            p = [i for i in range(n)]  # 集合
            s = [1] * n  # 集合数量

            def find(i):
                if p[i] != i:
                    p[i] = find(p[i])
                return p[i]

            for i in range(n):
                if id == i:
                    continue
                for j in range(i + 1, n):
                    if id == j:
                        continue
                    if graph[i][j] == 1:
                        if (pi := find(i)) != (pj := find(j)):
                            s[pi] += s[pj]
                            p[pj] = find(pi)
                            s[j] = 0
            ans = 0
            for i in initial:
                if i == id:
                    continue
                c = find(i)
                ans += s[c]
                s[c] = 0
            return ans

        ans = s = inf
        for i in initial:
            c = f(i)
            if c < s or c == s and ans > i:
                ans = i
                s = c
        return ans


s = Solution()
print(
    s.minMalwareSpread(
        [
            [1, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 0, 0, 0, 0, 0, 1],
            [0, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 1, 0, 0, 0, 0, 1],
            [0, 0, 0, 0, 1, 0, 1, 1, 1],
            [0, 0, 0, 0, 0, 1, 0, 0, 1],
            [0, 0, 0, 0, 1, 0, 1, 1, 0],
            [0, 0, 0, 0, 1, 0, 1, 1, 0],
            [0, 1, 0, 1, 1, 1, 0, 0, 1],
        ],
        [8, 4, 2, 0],
    )
)
